Problema 2 (Evadatul)

Un  prizonier al unei (nchisori a reu(it s( evadeze cu ajutorul unui complice 
care i-a trimis (i un plan al str(zilor din ora(. Complicele (l a(teapt( cu o 
ma(in( (ntr-una din intersec(iile ora(ului, pe care a marcat-o pe hart(. 
Pe acest plan complet al str(zilor (i intersec(iilor, sunt marcate distinct 
acele intersec(ii (n care se afl( posturile de control ale poli(iei locale, 
c(t (i punctul de plecare al proasp(tului evadat (care se afl( tot la o 
intersec(ie de str(zi). Pe hart( mai sunt marca(i (i timpii necesari pentru 
str(baterea fiec(rei str(zi. 
Evadatul (tie c( (n drumul s(u c(tre complice are voie s( (nt(lneasc( maxim 
m posturi de control. Altfel, la al m+1-lea post  va fi prins, deoarece el 
are la dispozi(ie numai m grenade pentru neutralizarea acestor puncte de 
control.
S( se determine drumul pe care evadatul trebuie s(-l str(bat( ca s( ajung( (n 
timpul cel mai scurt de la locul (n care se afl(, p(n( la complice. 
(n cazul (n care exist( mai multe drumuri cu acela(i timp minim de str(batere, 
evadatul (l va alege pe cel cu num(r minim de puncte de control. Pe hart( 
intersec(iile sunt numerotate cu numere de la 1 la n, consider(ndu-se 
intersec(ia num(rul 1 cea din care pleac( evadatul, (i intersec(ia num(rul n 
cea (n care se afl( complicele.
 	Fi(ierul de intrare al c(rui nume se cite(te de la tastatur(, are 
urm(toarea form(:
n		-num(r de intersec(ii, n<50
s		-num(r de str(zi
i1 j1 c1	-timpul c1 necesar pentru str(baterea str(zii aflate (ntre 
		intersec(iile i1 (i j1
i2 j2 c2	-timpul c2 necesar pentru str(baterea str(zii aflate (ntre 
		intersec(iile i2 (i j2
.
.
.
is js cs	-timpul cs necesar pentru str(baterea str(zii aflate (ntre intersec(iile is (i js
p		-num(rul de posturi de control
o1 o2 op	-lista intersec(iilor (n care se afl( puncte de control
m		-num(rul de grenade ( 10
(i con(ine numai valori naturale.
Fi(ierul de ie(ire va avea numele drum.txt  (i va con(ine pe prima linie 
intersec(iile aflate pe drumul cerut, iar pe linia a doua timpul necesar 
parcurgerii acestuia (i num(rul de puncte de control (nt(lnite.
Datele de pe fiecare linie a fi(ierului de ie(ire vor fi desp(r(ite prin 
exact un spa(iu.
(n cazul (n care nu exist( un astfel de drum, fi(ierul de ie(ire va con(ine 
mesajul
EVADAT CAPTURAT
Exemplu:
Fi(ierul de intrare
8
13
1 2 4
1 3 1
1 4 11
2 3 2
2 5 5
3 4 15
3 5 1
3 6 2
4 7 3
5 6 4
5 8 30
6 7 1
7 8 3
3
3 6 7
2
Fi(ierul de ie(ire:
1 4 7 8
17 1